<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        // 斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契
        // （Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列
        // ：0、1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：
        // F(0) = 0，F(1) = 1, F(n) = F(n - 1) + F(n - 2)（n ≥ 2，n ∈ N *）
        // 1.普通递归思想
        function fibonacci(n) {
                if (n == 0) {
                    return 0;
                }
                else if (n == 1) {
                    return 1;
                }
                return fibonacci(n - 1) + fibonacci(n - 2);
            }

            console.log(fibonacci(20));//6765
    // 存在大量的重复计算。如：当n为5的时候要计算fibonacci(4) + fibonacci(3)当n为4的要计算fibonacci(3) + fibonacci(2) 。
    // 优化
    function fib(n) {
            function fib_(n, a, b) {
                if (n == 0) {
                    return a;//0是第0项，a就是要找的最终的数
                }
                else {
                    return fib_(n - 1, b, a + b);
                    //每次将b赋值给a，避免了重复计算
                }
            }
            return fib_(n, 0, 1)
        }
        // 闭包
        const fibonacci = function () {
                var mem = [0, 1];
                var f = function (n) {
                    var res = mem[n];
                    if (typeof res !== 'number') {
                        mem[n] = f(n - 1) + f(n - 2);
                        res = mem[n];
                    }
                    return res;
                }
                return f;
            }();
    //箭头函数
    let fib = n => n > 1 ? fib(n - 1) + fib(n - 2) : n
//     爬楼梯
//     假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

// 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

//     注意：给定 n 是一个正整数。

// 示例 1：

//     输入： 2
//     输出： 2
//     解释： 有两种方法可以爬到楼顶。

//     1 阶 + 1 阶
//     2 阶
// 示例 2：
//     输入： 3
//     输出： 3
//     解释： 有三种方法可以爬到楼顶。
//递归
    //看了半天发现是斐波那契数列...
    //普通递归超出时间限制
    var climbStairs = function (n) {
        function fib_(n, a, b) {
            if (n == 1) {
                return a;
            }
            else {
                return fib_(n - 1, b, a + b);
                //每次将b赋值给a，避免了重复计算
            }
        }
        return fib_(n, 1, 2)
        // return climbStairs(n-1)+climbStairs(n-2);
    };
//循环
    //循环写试试
    var climbStairs = function (n) {
        if (n <= 2) { return n }
        let a = 1;
        let b = 2;
        let res = 0;
        for (let i = 3; i <= n; i++) {
            res = a + b;
            a = b;
            b = res;
        }
        return res;
    };


    </script>
</body>

</html>